{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Fruits Harvested After at Most K Steps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxTotalFruits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #摘水果"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 <code>fruits</code> ，其中 <code>fruits[i] = [position<sub>i</sub>, amount<sub>i</sub>]</code> 表示共有 <code>amount<sub>i</sub></code> 个水果放置在 <code>position<sub>i</sub></code> 上。<code>fruits</code> 已经按 <code>position<sub>i</sub></code> <strong>升序排列</strong> ，每个 <code>position<sub>i</sub></code> <strong>互不相同</strong> 。</p>\n",
    "\n",
    "<p>另给你两个整数 <code>startPos</code> 和 <code>k</code> 。最初，你位于 <code>startPos</code> 。从任何位置，你可以选择 <strong>向左或者向右</strong> 走。在 x 轴上每移动 <strong>一个单位</strong> ，就记作 <strong>一步</strong> 。你总共可以走 <strong>最多</strong> <code>k</code> 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。</p>\n",
    "\n",
    "<p>返回你可以摘到水果的 <strong>最大总数</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/21/1.png\" style=\"width: 472px; height: 115px;\">\n",
    "<pre><strong>输入：</strong>fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>\n",
    "最佳路线为：\n",
    "- 向右移动到位置 6 ，摘到 3 个水果\n",
    "- 向右移动到位置 8 ，摘到 6 个水果\n",
    "移动 3 步，共摘到 3 + 6 = 9 个水果\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/21/2.png\" style=\"width: 512px; height: 129px;\">\n",
    "<pre><strong>输入：</strong>fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4\n",
    "<strong>输出：</strong>14\n",
    "<strong>解释：</strong>\n",
    "可以移动最多 k = 4 步，所以无法到达位置 0 和位置 10 。\n",
    "最佳路线为：\n",
    "- 在初始位置 5 ，摘到 7 个水果\n",
    "- 向左移动到位置 4 ，摘到 1 个水果\n",
    "- 向右移动到位置 6 ，摘到 2 个水果\n",
    "- 向右移动到位置 7 ，摘到 4 个水果\n",
    "移动 1 + 3 = 4 步，共摘到 7 + 1 + 2 + 4 = 14 个水果\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/11/21/3.png\" style=\"width: 476px; height: 100px;\">\n",
    "<pre><strong>输入：</strong>fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "最多可以移动 k = 2 步，无法到达任一有水果的地方\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= fruits.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>fruits[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= startPos, position<sub>i</sub> &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "\t<li>对于任意 <code>i &gt; 0</code> ，<code>position<sub>i-1</sub> &lt; position<sub>i</sub></code> 均成立（下标从 <strong>0</strong> 开始计数）</li>\n",
    "\t<li><code>1 &lt;= amount<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 2 * 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-fruits-harvested-after-at-most-k-steps](https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-fruits-harvested-after-at-most-k-steps](https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,8],[6,3],[8,6]]\\n5\\n4', '[[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]]\\n5\\n4', '[[0,3],[6,4],[8,5]]\\n3\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, a: List[List[int]], b: int, k: int) -> int:\n",
    "        n = len(a)\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        r = 0\n",
    "        def get_step(l,p):\n",
    "            if p<=b:\n",
    "                step = b - a[l][0]\n",
    "            elif a[l][0]>=b:\n",
    "                step = p-b\n",
    "            else:\n",
    "                step = p - a[l][0]+min(p-b,b-a[l][0])\n",
    "            return step\n",
    "        for right,(p,amout) in enumerate(a):\n",
    "            ans+=amout\n",
    "            step = get_step(left,p)\n",
    "            print(\"from\",step,left,right)\n",
    "            while left<=right and step>k:\n",
    "                ans -=a[left][1]\n",
    "                left+=1\n",
    "                if left>=n:\n",
    "                    break\n",
    "                step = get_step(left,p)\n",
    "            print(\"to\",step,left,right,ans)\n",
    "            if step<=k:\n",
    "                r = max(r,ans)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        # 枚举向左走了几步就完事\n",
    "        # [startPos-step, startPos+k-2*step]\n",
    "        \n",
    "        locations = [x for x, y in fruits]\n",
    "        nums = [y for x, y in fruits]\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        \n",
    "        ans = 0\n",
    "        for step in range(k+1):\n",
    "            left = startPos-step\n",
    "            right = max(startPos, startPos+k-2*step)\n",
    "            i = bisect_left(locations, left)\n",
    "            j = bisect_right(locations, right)\n",
    "            ans = max(ans, pre[j]-pre[i])\n",
    "        for step in range(k+1):\n",
    "            right = startPos+step\n",
    "            left = startPos-max(0, k-2*step)\n",
    "            i = bisect_left(locations, left)\n",
    "            j = bisect_right(locations, right)\n",
    "            ans = max(ans, pre[j]-pre[i])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, a: List[List[int]], b: int, k: int) -> int:\n",
    "        n = len(a)\n",
    "        left = 0\n",
    "        ans = 0\n",
    "        r = 0\n",
    "        def get_step(l,p):\n",
    "            if p<=b:\n",
    "                step = b - a[l][0]\n",
    "            elif a[l][0]>=b:\n",
    "                step = p-b\n",
    "            else:\n",
    "                step = p - a[l][0]+min(p-b,b-a[l][0])\n",
    "            return step\n",
    "        for right,(p,amout) in enumerate(a):\n",
    "            ans+=amout\n",
    "            step = get_step(left,p)\n",
    "            print(\"from\",step,left,right)\n",
    "            while left<=right and step>k:\n",
    "                ans -=a[left][1]\n",
    "                left+=1\n",
    "                if left>=n:\n",
    "                    break\n",
    "                step = get_step(left,p)\n",
    "            print(\"to\",step,left,right,ans)\n",
    "            if step<=k:\n",
    "                r = max(r,ans)\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        result = 0\n",
    "        #初始化慢指针\n",
    "        left = 0\n",
    "        tmp = 0 \n",
    "        #i表示左下标\n",
    "        #j表示右下标\n",
    "        #for 快指针 in 可迭代集合\n",
    "        for right, (position, amount) in enumerate(fruits):\n",
    "            #fruits[left][0]表示左边的位置\n",
    "            #fruits[right][0]表示右边的位置\n",
    "            tmp += amount\n",
    "            while left <= right and position - fruits[left][0] + min(abs(startPos - fruits[left][0]), abs(startPos - position)) > k:\n",
    "                tmp -= fruits[left][1]\n",
    "                left += 1\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = right = 0\n",
    "        n = len(fruits)\n",
    "        sum = ans = 0\n",
    "        def computeStep(left: int, right: int) -> int:\n",
    "            return min(abs(startPos - fruits[right][0]), abs(startPos - fruits[left][0])) + fruits[right][0] - fruits[left][0]\n",
    "        while right < n:\n",
    "            sum += fruits[right][1]\n",
    "            while left <= right and computeStep(left, right) > k:\n",
    "                sum -= fruits[left][1]\n",
    "                left += 1\n",
    "            right += 1\n",
    "            ans = max(ans, sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        result = 0\n",
    "        left = 0\n",
    "        tmp = 0 \n",
    "        #i表示左下标\n",
    "        #j表示右下标\n",
    "        for right, (position, amount) in enumerate(fruits):\n",
    "            #fruits[i][0]表示左边的位置\n",
    "            #fruits[j][0]表示右边的位置\n",
    "            #fj表示草莓的数量\n",
    "            tmp += amount\n",
    "            while left <= right and position - fruits[left][0] + min(abs(startPos - fruits[left][0]), abs(startPos - fruits[right][0])) > k:\n",
    "                tmp -= fruits[left][1]\n",
    "                left += 1\n",
    "            result = max(result, tmp)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits, startPos, k):\n",
    "        n = len(fruits)\n",
    "        sum = [0] * (n + 1)\n",
    "        indices = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            sum[i + 1] = sum[i] + fruits[i][1]\n",
    "            indices[i] = fruits[i][0]\n",
    "\n",
    "        ans = 0\n",
    "        for x in range(k // 2 + 1):\n",
    "            # 向左走 x 步，再向右走 k - x 步\n",
    "            y = k - 2 * x\n",
    "            left = startPos - x\n",
    "            right = startPos + y\n",
    "            start = bisect.bisect_left(indices, left)\n",
    "            end = bisect.bisect_right(indices, right)\n",
    "            ans = max(ans, sum[end] - sum[start])\n",
    "\n",
    "            # 向右走 x 步，再向左走 k - x 步\n",
    "            y = k - 2 * x\n",
    "            left = startPos - y\n",
    "            right = startPos + x\n",
    "            start = bisect.bisect_left(indices, left)\n",
    "            end = bisect.bisect_right(indices, right)\n",
    "            ans = max(ans, sum[end] - sum[start])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        # 枚举能走到的最左边\n",
    "        left = -1\n",
    "        for i, x in enumerate(fruits):\n",
    "            if x[0] >= startPos - k:\n",
    "                left = i\n",
    "                break\n",
    "        if left == -1:\n",
    "            return 0\n",
    "        ans, s = 0, 0\n",
    "        for right, p in fruits[left:]:\n",
    "            if right > startPos + k:\n",
    "                break\n",
    "            s += p\n",
    "            # 判断走的总距离是否合法, 无论什么方向\n",
    "            while right * 2 - startPos - fruits[left][0] > k and \\\n",
    "            startPos - fruits[left][0] * 2 + right > k:   \n",
    "                s -= fruits[left][1]\n",
    "                left += 1\n",
    "            ans = max(ans, s)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        # def lowerBound(arr, left, right, val):\n",
    "        #     res = right + 1\n",
    "        #     while left <= right:\n",
    "        #         mid = left + (right - left) // 2\n",
    "        #         if arr[mid] >= val:\n",
    "        #             res = mid\n",
    "        #             right = mid - 1\n",
    "        #         else:\n",
    "        #             left = mid + 1\n",
    "        #     return res\n",
    "        \n",
    "        # def upperBound(arr, left, right, val):\n",
    "        #     res = right + 1\n",
    "        #     while left <= right:\n",
    "        #         mid = left + (right - left) // 2\n",
    "        #         if arr[mid] > val:\n",
    "        #             res = mid\n",
    "        #             right = mid - 1\n",
    "        #         else:\n",
    "        #             left = mid + 1\n",
    "        #     return res\n",
    "        n = len(fruits)\n",
    "        sum = [0 for i in range(n+1)]\n",
    "        indices = []\n",
    "        for i in range(n):\n",
    "            sum[i+1] = sum[i] + fruits[i][1]\n",
    "            indices.append(fruits[i][0])\n",
    "        res = 0\n",
    "        for x in range(k//2+1):  # left\n",
    "            y = k - 2 * x\n",
    "            left = startPos - x\n",
    "            right = startPos + y\n",
    "            # start = lowerBound(indices, 0, n-1, left)\n",
    "            # end = upperBound(indices, 0, n-1, right)\n",
    "            start = bisect_left(indices, left)\n",
    "            end = bisect_right(indices, right)\n",
    "            res = max(res, sum[end] - sum[start])\n",
    "            \n",
    "            y = k - 2 * x\n",
    "            left = startPos - y\n",
    "            right = startPos + x\n",
    "            # start = lowerBound(indices, 0, n-1, left)\n",
    "            # end = upperBound(indices, 0, n-1, right)\n",
    "            start = bisect_left(indices, left)\n",
    "            end = bisect_right(indices, right)\n",
    "            res = max(res, sum[end] - sum[start])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])\n",
    "        right = bisect_left(fruits, [startPos + 1]) # right是开\n",
    "        ans = s = sum(c for _, c in fruits[left:right])\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and fruits[right][0] - fruits[left][0] * 2 + startPos > k: \n",
    "                s -= fruits[left][1] # fruits[left][0]无法到达\n",
    "                left += 1\n",
    "            ans = max(ans, s)\n",
    "            right += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])\n",
    "        right = bisect_left(fruits, [startPos + 1])\n",
    "        res = s = sum(c for _,c in fruits[left: right])\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and fruits[right][0] - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1]\n",
    "                left += 1\n",
    "            res = max(res, s)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = right = 0\n",
    "        n = len(fruits)\n",
    "        sum = ans = 0\n",
    "        def computeStep(left: int, right: int) -> int:\n",
    "            return min(abs(startPos - fruits[right][0]), abs(startPos - fruits[left][0])) + fruits[right][0] - fruits[left][0]\n",
    "        while right < n:\n",
    "            sum += fruits[right][1]\n",
    "            while left <= right and computeStep(left, right) > k:\n",
    "                sum -= fruits[left][1]\n",
    "                left += 1\n",
    "            right += 1\n",
    "            ans = max(ans, sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        left = right = 0\n",
    "        while left+1<n and fruits[left+1][0] < startPos - k:\n",
    "            left += 1\n",
    "            right += 1\n",
    "        t = 0\n",
    "        # while right<n and fruits[right][0] < startPos:\n",
    "        #     t += fruits[right][1]\n",
    "        #     right+=1\n",
    "        r = t\n",
    "        #print(t,left,right)\n",
    "        while left<=right<n:\n",
    "            while left<=right<n and 0<=min(abs(fruits[right][0]-startPos),abs(startPos-fruits[left][0]))+ fruits[right][0]-fruits[left][0]<=k:\n",
    "                #print(min(fruits[right][0]-startPos,startPos-fruits[left][0])+ fruits[right][0]-fruits[left][0])\n",
    "                t+=fruits[right][1]\n",
    "                right+=1\n",
    "            r = max(r,t)\n",
    "            if right>left:t -= fruits[left][1]\n",
    "            left+=1\n",
    "            if left>right:right+=1\n",
    "            #print(1111111,t,left,right)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        def calc(l,r) :\n",
    "            if fruits[r][0] <= startPos :\n",
    "                return startPos - fruits[l][0]\n",
    "            elif fruits[l][0] >= startPos :\n",
    "                return fruits[r][0] - startPos\n",
    "            return min(fruits[r][0] - startPos + fruits[r][0] - fruits[l][0], startPos - fruits[l][0] + fruits[r][0] - fruits[l][0])\n",
    "\n",
    "\n",
    "        l,r = 0,0\n",
    "        n = len(fruits)\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        while r < n :\n",
    "            cur += fruits[r][1]\n",
    "            while l <= r and calc(l,r) > k :\n",
    "                cur -= fruits[l][1]\n",
    "                l += 1\n",
    "            res = max(res,cur)\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        #记录结果\n",
    "        result = 0\n",
    "        #初始化慢指针\n",
    "        left = 0\n",
    "        #记录水果数\n",
    "        tmp = 0 \n",
    "        #for 快指针 in 可迭代集合\n",
    "        for right, (position, amount) in enumerate(fruits):\n",
    "            #fruits[left][0]表示左边的位置\n",
    "            #fruits[right][0]表示右边的位置\n",
    "            tmp += amount\n",
    "            #不满足条件时，收缩窗口，慢指针移动\n",
    "            #right - left + min(abs(startPos - leftPosition), abs(startPos - rightPosition))\n",
    "            while left <= right and position - fruits[left][0] + min(abs(startPos - fruits[left][0]), abs(startPos - position)) > k:\n",
    "                tmp -= fruits[left][1]\n",
    "                left += 1\n",
    "            #更新答案\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        #解题关键在于，需要想到从startPos开始，走完一个特定区间里的所有positions的最小步数是确定的，这个最小步数只和那个区间的左右边界相关。\n",
    "        def cost(lower, upper):\n",
    "            #返回startPos开始，走完[lower,upper]区间所需的最小步数'''\n",
    "            return min(abs(startPos-lower), abs(startPos-upper))+upper-lower\n",
    "        \n",
    "        # 滑动窗口区间[left,right]，winSum为区间内的草莓总数\n",
    "        left, right, winSum = 0, 0, 0\n",
    "        ans = 0\n",
    "        while right < len(fruits):\n",
    "            winSum += fruits[right][1]\n",
    "            while cost(fruits[left][0], fruits[right][0]) > k and left < right:\n",
    "                winSum -= fruits[left][1]\n",
    "                left += 1\n",
    "            if cost(fruits[left][0], fruits[right][0]) > k:\n",
    "                # 若当前窗口不可及，窗口左右指针要一起移动\n",
    "                winSum -= fruits[left][1]\n",
    "                right += 1\n",
    "                left += 1\n",
    "            else:\n",
    "                ans = max(ans, winSum)\n",
    "                right += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]\n",
    "        right = bisect_left(fruits, [startPos + 1])  # startPos 右边最近水果（因为下面求的是左闭右开区间）\n",
    "        ans = s = sum(c for _, c in fruits[left:right])  # 从 fruits[left][0] 到 startPos 的水果数\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]  # 枚举最右位置为 fruits[right][0]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and \\\n",
    "                  fruits[right][0] - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1]  # fruits[left][0] 无法到达\n",
    "                left += 1\n",
    "            ans = max(ans, s)  # 更新答案最大值\n",
    "            right += 1  # 继续枚举下一个最右位置\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = right = 0\n",
    "        n = len(fruits)\n",
    "        sum = ans = 0\n",
    "        def computeStep(left: int, right: int) -> int:\n",
    "            return min(abs(startPos - fruits[right][0]), abs(startPos - fruits[left][0])) + fruits[right][0] - fruits[left][0]\n",
    "        while right < n:\n",
    "            sum += fruits[right][1]\n",
    "            while left <= right and computeStep(left, right) > k:\n",
    "                sum -= fruits[left][1]\n",
    "                left += 1\n",
    "            right += 1\n",
    "            ans = max(ans, sum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        #记录结果\n",
    "        result = 0\n",
    "        #初始化慢指针\n",
    "        left = 0\n",
    "        #记录水果数\n",
    "        tmp = 0 \n",
    "        #for 快指针 in 可迭代集合\n",
    "        for right, (position, amount) in enumerate(fruits):\n",
    "            #fruits[left][0]表示左边的位置\n",
    "            #fruits[right][0]表示右边的位置\n",
    "            tmp += amount\n",
    "            #不满足条件时，收缩窗口，慢指针移动\n",
    "            #right - left + min(abs(startPos - leftPosition), abs(startPos - rightPosition))表示的是该区间的最小步数\n",
    "            while left <= right and position - fruits[left][0] + min(abs(startPos - fruits[left][0]), abs(startPos - position)) > k:\n",
    "                tmp -= fruits[left][1]\n",
    "                left += 1\n",
    "            #更新答案\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "\n",
    "        pres = [0]\n",
    "        c = [(p, f) for p, f in fruits]\n",
    "        for i in range(len(fruits)):\n",
    "            pres.append(pres[-1] + fruits[i][1])\n",
    "        ans = 0\n",
    "        mp = fruits[-1][0]\n",
    "        mi = fruits[0][0]\n",
    "        if startPos >= mi:\n",
    "            for l in range(min(k, startPos) + 1):\n",
    "                r = max(startPos, startPos + (k - 2 * l))\n",
    "                i = bisect_left(c, (startPos, inf))\n",
    "                j = bisect_left(c, (startPos - l, -inf))\n",
    "                cur = pres[i] - pres[j]\n",
    "                rdx = bisect_left(c, (r, inf))\n",
    "                cur += pres[rdx] - pres[i]\n",
    "                ans = max(ans, cur)\n",
    "                # print(l, r, ans, i, j, rdx)\n",
    "\n",
    "        if startPos <= mp:\n",
    "            for r in range(min(k, mp - startPos) + 1):\n",
    "                l = min(startPos, max(0, startPos - (k - 2 * r)))\n",
    "                i = bisect_left(c, (startPos + r, inf))\n",
    "                j = bisect_left(c, (startPos, -inf))\n",
    "                cur = pres[i] - pres[j]\n",
    "                ldx = bisect_left(c, (l, -inf))\n",
    "                cur += pres[j] - pres[ldx]\n",
    "                ans = max(ans, cur)\n",
    "                # print(l, r, ans, i, j, rdx)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        pos = [i[0] for i in fruits]\n",
    "        res = 0\n",
    "        for i in range(1, n + 1):\n",
    "            pre_sum[i] += fruits[i - 1][1] + pre_sum[i - 1]\n",
    "\n",
    "        for x in range(k, -1, -1):\n",
    "            y = (k - x) // 2\n",
    "            l, r = startPos - x, startPos + y\n",
    "            pl, pr = bisect.bisect_left(pos, l), bisect.bisect_right(pos, r)\n",
    "            res = max(res, pre_sum[pr] - pre_sum[pl])\n",
    "            \n",
    "            l, r = startPos - y, startPos + x\n",
    "            pl, pr = bisect.bisect_left(pos, l), bisect.bisect_right(pos, r)\n",
    "            res = max(res, pre_sum[pr] - pre_sum[pl])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        n = len(fruits)\n",
    "        sum = 0\n",
    "        ans = 0\n",
    "\n",
    "        def step(left: int, right: int) -> int:\n",
    "            if fruits[right][0] <= startPos:\n",
    "                return startPos - fruits[left][0]\n",
    "            elif fruits[left][0] >= startPos:\n",
    "                return fruits[right][0] - startPos\n",
    "            else:\n",
    "                return min(abs(startPos - fruits[right][0]), abs(startPos - fruits[left][0])) + \\\n",
    "                    fruits[right][0] - fruits[left][0]\n",
    "\n",
    "        # 每次固定住窗口右边界\n",
    "        while right < n:\n",
    "            sum += fruits[right][1]\n",
    "            # 移动左边界\n",
    "            while left <= right and step(left, right) > k:\n",
    "                sum -= fruits[left][1]\n",
    "                left += 1\n",
    "\n",
    "            ans = max(ans, sum)\n",
    "            right += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        #记录结果\n",
    "        result = 0\n",
    "        #初始化慢指针\n",
    "        left = 0\n",
    "        #记录水果数\n",
    "        tmp = 0 \n",
    "        #for 快指针 in 可迭代集合\n",
    "        for right, (position, amount) in enumerate(fruits):\n",
    "            #fruits[left][0]表示左边的位置\n",
    "            #fruits[right][0]表示右边的位置\n",
    "            tmp += amount\n",
    "            #不满足条件时，收缩窗口，慢指针移动\n",
    "            #right - left + min(abs(startPos - leftPosition), abs(startPos - rightPosition))表示的是该区间的最小步数\n",
    "            while left <= right and position - fruits[left][0] + min(abs(startPos - fruits[left][0]), abs(startPos - position)) > k:\n",
    "                tmp -= fruits[left][1]\n",
    "                left += 1\n",
    "            #更新答案\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "\n",
    "        n = len(fruits)\n",
    "        #fruits.sort() \n",
    "\n",
    "        if n == 1:\n",
    "            if startPos - k <= fruits[0][0] <= startPos + k:\n",
    "                return fruits[0][1]\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        f = [0] * (n + 1) \n",
    "        for i in range(1, n+1):\n",
    "            f[i] = f[i-1] + fruits[i-1][1] \n",
    "        \n",
    "        def lower_bound(x, l, r):\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1 \n",
    "                if fruits[mid][0] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l \n",
    "        \n",
    "\n",
    "        # left -> right. \n",
    "        ans = 0\n",
    "        for kk in range(k//2+1):\n",
    "            left = lower_bound(startPos-kk, 0, n) \n",
    "            right = lower_bound(startPos+k - kk*2+1, 0, n) \n",
    "            ans = max(ans, f[right] - f[left])\n",
    "        \n",
    "        # right -> left \n",
    "        for kk in range(k//2+1):\n",
    "            left = lower_bound(startPos - k + kk * 2, 0, n) \n",
    "            right = lower_bound(startPos + kk+1, 0, n) \n",
    "            ans = max(ans, f[right] - f[left]) \n",
    "        \n",
    "        return ans  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])\n",
    "        right = bisect_left(fruits, [startPos + 1])\n",
    "        ans = s = sum(c for _, c in fruits[left:right])\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and fruits[right][0] - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1]\n",
    "                left += 1\n",
    "            ans = max(ans, s)\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        \"\"\"\n",
    "        核心算法：滑动窗口,\n",
    "        题目模型：首先我们要明确最优解的pattern，一定是往一个方向走x步到A，再返回起点（必然同样走了x步），再往另一个方向走y步到B。需要满足的约束\n",
    "        是2x+y<=k. 注意，其中x不是必须的，可以为0.\n",
    "        \"\"\"\n",
    "        ans = 0\n",
    "\n",
    "        left_idx = bisect.bisect_left(fruits, [startPos - k])\n",
    "        right_idx = bisect.bisect_left(fruits, [startPos + 1])\n",
    "        slide_sum = sum([v for _, v in fruits[left_idx: right_idx]])\n",
    "        ans = slide_sum\n",
    "        # 枚举right_idx\n",
    "        while right_idx < len(fruits) and fruits[right_idx][0] <= startPos + k:\n",
    "            slide_sum += fruits[right_idx][1]\n",
    "            \n",
    "            # 移动left_idx\n",
    "            while (fruits[right_idx][0] - fruits[left_idx][0] + fruits[right_idx][0] - startPos) > k \\\n",
    "                    and (fruits[right_idx][0] - fruits[left_idx][0] + startPos - fruits[left_idx][0]) > k:\n",
    "                slide_sum -= fruits[left_idx][1]\n",
    "                left_idx += 1\n",
    "            ans = max(ans, slide_sum)\n",
    "            \n",
    "            right_idx += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]\n",
    "        right = bisect_left(fruits, [startPos + 1])  # startPos 右边最近水果（因为下面求的是左闭右开区间）\n",
    "        ans = s = sum(c for _, c in fruits[left:right])  # 从 fruits[left][0] 到 startPos 的水果数\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]  # 枚举最右位置为 fruits[right][0]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and \\\n",
    "                  fruits[right][0] - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1]  # fruits[left][0] 无法到达\n",
    "                left += 1\n",
    "            ans = max(ans, s)  # 更新答案最大值\n",
    "            right += 1  # 继续枚举下一个最右位置\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        result = 0\n",
    "        left = 0\n",
    "        tmp = 0 \n",
    "        #i表示左下标\n",
    "        #j表示右下标\n",
    "        for right, (position, amount) in enumerate(fruits):\n",
    "            #fruits[i][0]表示左边的位置\n",
    "            #fruits[j][0]表示右边的位置\n",
    "            #fj表示草莓的数量\n",
    "            tmp += amount\n",
    "            while left <= right and position - fruits[left][0] + min(abs(startPos - fruits[left][0]), abs(startPos - fruits[right][0])) > k:\n",
    "                tmp -= fruits[left][1]\n",
    "                left += 1\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n=len(fruits)\n",
    "        left=bisect_left(fruits,[startPos-k])\n",
    "        right=bisect_left(fruits,[startPos+1])\n",
    "        res=temp=sum(j for i,j in fruits[left:right])\n",
    "        while right<n and fruits[right][0]<=startPos+k:\n",
    "            temp+=fruits[right][1]\n",
    "            while fruits[right][0]-fruits[left][0]+fruits[right][0]-startPos>k and fruits[right][0]-fruits[left][0]+startPos-fruits[left][0]>k:\n",
    "                temp-=fruits[left][1]\n",
    "                left+=1\n",
    "            res=max(res,temp)\n",
    "            right+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        # 解题关键在于，需要想到从startPos开始，走完一个特定区间里的所有positions的最小步数是确定的，这个最小步数只和那个区间的左右边界相关。\n",
    "        def cost(lower, upper):\n",
    "            # 返回startPos开始，走完[lower,upper]区间所需的最小步数\n",
    "            return min(abs(startPos-lower), abs(startPos-upper))+upper-lower\n",
    "        \n",
    "        # 滑动窗口区间[left,right]，winSum为区间内的草莓总数\n",
    "        left, right, winSum = 0, 0, 0\n",
    "        # 正确答案和\n",
    "        ans = 0\n",
    "        while right < len(fruits):\n",
    "            # 总体采摘的苹果数量和\n",
    "            winSum += fruits[right][1]\n",
    "            # 如果滑动窗口区间所需最小步数大于k且窗口长度大于1 收缩窗口\n",
    "            while cost(fruits[left][0], fruits[right][0]) > k and left < right:\n",
    "                winSum -= fruits[left][1]\n",
    "                left += 1\n",
    "            # 如果滑动窗口区间所需最小步数大于k且窗口长度等于1 整体滑动窗口\n",
    "            if cost(fruits[left][0], fruits[right][0]) > k:\n",
    "                # 若当前窗口不可及，窗口左右指针要一起移动\n",
    "                winSum -= fruits[left][1]\n",
    "                right += 1\n",
    "                left += 1\n",
    "            # 如果滑动窗口区间所需最小步数小于等于k\n",
    "            else:\n",
    "                # 如果滑动窗口区间内的草莓总数大于ans，则更新ans\n",
    "                ans = max(ans, winSum)\n",
    "                # 右指针移动 扩张窗口\n",
    "                right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        def cost(lower, upper):\n",
    "            #返回startPos开始，走完[lower,upper]区间所需的最小步数'''\n",
    "            return min(abs(startPos-lower), abs(startPos-upper))+upper-lower\n",
    "        \n",
    "        # 滑动窗口区间[left,right]，winSum为区间内的草莓总数\n",
    "        left, right, winSum = 0, 0, 0\n",
    "        ans = 0\n",
    "        while right < len(fruits):\n",
    "            winSum += fruits[right][1]\n",
    "            while cost(fruits[left][0], fruits[right][0]) > k and left < right:\n",
    "                winSum -= fruits[left][1]\n",
    "                left += 1\n",
    "            if cost(fruits[left][0], fruits[right][0]) > k:\n",
    "                # 若当前窗口不可及，窗口左右指针要一起移动\n",
    "                winSum -= fruits[left][1]\n",
    "                right += 1\n",
    "                left += 1\n",
    "            else:\n",
    "                ans = max(ans, winSum)\n",
    "                right += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        ans = 0\n",
    "        for x, y in fruits:\n",
    "            if x <= startPos and startPos - x <= k:\n",
    "                ans += y\n",
    "        j = bisect_left(fruits, startPos, key=lambda x:x[0])\n",
    "        if j != n and fruits[j][0] >= startPos:\n",
    "            i = j\n",
    "            tot = 0\n",
    "            while j < n:\n",
    "                if fruits[j][0] - startPos <= k:\n",
    "                    tot += fruits[j][1]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans = max(ans, tot)\n",
    "            j -= 1\n",
    "            t = i - 1\n",
    "            #print(\"j = \", j)\n",
    "            while j >= 0 and fruits[j][0] >= startPos:\n",
    "                left = k - (fruits[j][0] - startPos)\n",
    "                #print(left)\n",
    "                if left > 0:\n",
    "                    while t >= 0:\n",
    "                        if (startPos - fruits[t][0]) * 2 <= left or startPos - fruits[t][0] + 2 * (fruits[j][0] - startPos) <= k:\n",
    "                            tot += fruits[t][1]\n",
    "                            t -= 1\n",
    "                        else:\n",
    "                            break\n",
    "                    ans = max(ans, tot)\n",
    "                tot -= fruits[j][1]\n",
    "                j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        \n",
    "        ans=0\n",
    "        l=0\n",
    "        n=len(fruits)\n",
    "        s=0\n",
    "        for r in range(n):\n",
    "            p=fruits[r][0]\n",
    "            v=fruits[r][1]\n",
    "            s=s+v\n",
    "            while l<=r and p-fruits[l][0] +min( abs(startPos-fruits[l][0]),abs(startPos-p))>k:\n",
    "                s=s-fruits[l][1]\n",
    "                l=l+1\n",
    "            ans=max(ans,s)\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        ps = list(accumulate([x[1] for x in fruits],initial = 1))\n",
    "        a = [x[0] for x in fruits]\n",
    "        ans = 0\n",
    "        # x*2 + y = k\n",
    "        for y in range(k + 1):\n",
    "            x = (k - y) // 2\n",
    "            l,r = startPos - x,startPos + y\n",
    "            l,r = bisect_left(a,l),bisect_right(a,r)\n",
    "            ans = max(ans,ps[r] - ps[l])\n",
    "\n",
    "            l,r = startPos - y,startPos + x\n",
    "            l,r = bisect_left(a,l),bisect_right(a,r)\n",
    "            ans = max(ans,ps[r] - ps[l])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        pre = [0] * (n+1)\n",
    "        pos = []\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = pre[i-1] + fruits[i-1][1]\n",
    "            pos.append(fruits[i-1][0])\n",
    "        ans = 0 \n",
    "        for i in range(k//2+1):\n",
    "            left = i \n",
    "            right = k - 2 * i \n",
    "            idx1 = bisect_left(pos, startPos - left) \n",
    "            idx2 = bisect_left(pos, startPos + right +1) \n",
    "            ans = max(ans, pre[idx2] - pre[idx1])\n",
    "        for i in range(k//2+1):\n",
    "            right = i \n",
    "            left = k - 2 * i \n",
    "            idx1 = bisect_left(pos, startPos - left) \n",
    "            idx2 = bisect_left(pos, startPos + right +1) \n",
    "            ans = max(ans, pre[idx2] - pre[idx1]) \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        indices=[]\n",
    "        temp_sum=0\n",
    "        fruits_sum=[0]\n",
    "        for fruit in fruits:\n",
    "            indices.append(fruit[0])\n",
    "            temp_sum+=fruit[1]\n",
    "            fruits_sum.append(temp_sum)\n",
    "        ans=0\n",
    "        for x in range(k//2+1):\n",
    "            left=startPos-x\n",
    "            right=startPos+k-2*x\n",
    "            st=bisect.bisect_left(indices, left)\n",
    "            ed=bisect.bisect_right(indices, right)\n",
    "            ans=max(ans, fruits_sum[ed]-fruits_sum[st])\n",
    "            left=startPos-k+2*x\n",
    "            right=startPos+x\n",
    "            st=bisect.bisect_left(indices, left)\n",
    "            ed=bisect.bisect_right(indices, right)\n",
    "            ans=max(ans, fruits_sum[ed]-fruits_sum[st])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left=bisect_left(fruits,[startPos-k])\n",
    "        right=bisect_left(fruits,[startPos+1])\n",
    "        ans=s=sum(c for _,c in fruits[left:right])\n",
    "        while right< len(fruits) and fruits[right][0]<=startPos+k:\n",
    "            s+=fruits[right][1]\n",
    "            while 2*fruits[right][0]-fruits[left][0]-startPos>k and fruits[right][0]-2*fruits[left][0]+startPos>k:\n",
    "                s-=fruits[left][1]\n",
    "                left+=1\n",
    "            ans=max(ans,s)\n",
    "            right+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def lowbit(x):\n",
    "    return x & -x\n",
    "\n",
    "class BitTree:\n",
    "    def __init__(self,n):\n",
    "        self.F = [0] * (n+1)\n",
    "        self.n = n + 1\n",
    "\n",
    "    def update(self,pos,v):\n",
    "        pos += 1\n",
    "        while pos < self.n:\n",
    "            self.F[pos] += v\n",
    "            pos += lowbit(pos)\n",
    "    \n",
    "    def query(self,pos):\n",
    "        pos += 1\n",
    "        if not pos:return 0\n",
    "        res = 0\n",
    "        while pos > 0:\n",
    "            res += self.F[pos]\n",
    "            pos -= lowbit(pos)\n",
    "        return res\n",
    "    \n",
    "    def qab(self,a,b): #[a,b]\n",
    "        return self.query(b) - self.query(a-1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = max([a for a,b in fruits])+1\n",
    "        Tr = BitTree(n)\n",
    "        for a,b in fruits:\n",
    "            Tr.update(a,b)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if i + k < startPos or i - k > startPos:continue\n",
    "            if i <= startPos and i + k >= startPos:\n",
    "                r = min(n-1,startPos + (i+k-startPos)//2)\n",
    "                res = max(res,Tr.qab(i,r))\n",
    "            if i >= startPos and i - k <= startPos:\n",
    "                l = max(0,startPos - (startPos-i+k)//2)\n",
    "                res = max(res,Tr.qab(l,i))\n",
    "                \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]\n",
    "        right = bisect_left(fruits, [startPos + 1])  # startPos 右边最近水果（因为下面求的是左闭右开区间）\n",
    "        ans = s = sum(c for _, c in fruits[left:right])  # 从 fruits[left][0] 到 startPos 的水果数\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]  # 枚举最右位置为 fruits[right][0]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and \\\n",
    "                  fruits[right][0] - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1]  # fruits[left][0] 无法到达\n",
    "                left += 1\n",
    "            ans = max(ans, s)  # 更新答案最大值\n",
    "            right += 1  # 继续枚举下一个最右位置\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        # 所以最优方案要么先向右再向左，要么先向左再向右（或者向一个方向走到底）\n",
    "        # 左边最远 startPos - k\n",
    "        # 右边最远 startPos + k\n",
    "        # 先从固定left = 左边第一个，right等于右边第一个，当startPos 右边最近水果（因为下面求的是左闭右开区间\n",
    "        left = bisect.bisect_left(fruits,[startPos-k])\n",
    "        right = bisect.bisect_left(fruits,[startPos+1])\n",
    "        ans = s = sum (c for _, c in fruits[left:right]) #此时right对应的水果还没收取\n",
    "        #采用先左移后右移，先右移再左移的方式滑动窗口\n",
    "        \n",
    "        while right<len(fruits) and fruits[right][0] - startPos <= k:\n",
    "            s += fruits[right][1] #加上right位置的水果\n",
    "            while startPos+fruits[right][0]-2*fruits[left][0] >k and 2*fruits[right][0]-startPos- fruits[left][0] >k: #两种移动方式都大于k,此时路径太长，需要收缩区间，left需要左移\n",
    "                s -= fruits[left][1]\n",
    "                left += 1\n",
    "            ans = max(ans,s)\n",
    "            right += 1\n",
    "        return ans \n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "\n",
    "        left = bisect_left(fruits, [startPos - k]) # 向左最远能到fruits[left][0]\n",
    "        right = bisect_left(fruits, [startPos + 1])  # startPos右边最近水果 \n",
    "        ans = s = sum(c for _, c in fruits[left:right]) # 从fruits[left][0]到startPos的水果数\n",
    "\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1] # 枚举最优位置为fruits[right][0]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and \\\n",
    "                fruits[right][0] - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1] # fruits[left][0] 无法到达\n",
    "                left += 1\n",
    "            ans = max(ans, s) # 更新答案最大值\n",
    "            right += 1 # 继续枚举下一个最有位置\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]\n",
    "        right = bisect_left(fruits, [startPos + 1])  # startPos 右边最近水果（因为下面求的是左闭右开区间）\n",
    "        ans = s = sum(c for _, c in fruits[left:right])  # 从 fruits[left][0] 到 startPos 的水果数\n",
    "        while right < len(fruits) and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]  # 枚举最右位置为 fruits[right][0]\n",
    "            while fruits[right][0] * 2 - fruits[left][0] - startPos > k and \\\n",
    "                  fruits[right][0] - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1]  # fruits[left][0] 无法到达\n",
    "                left += 1\n",
    "            ans = max(ans, s)  # 更新答案最大值\n",
    "            right += 1  # 继续枚举下一个最右位置\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        ans = 0\n",
    "        for x, y in fruits:\n",
    "            if x <= startPos and startPos - x <= k:\n",
    "                ans += y\n",
    "        j = bisect_left(fruits, startPos, key=lambda x:x[0])\n",
    "        if j != n and fruits[j][0] >= startPos:\n",
    "            i = j\n",
    "            tot = 0\n",
    "            while j < n:\n",
    "                if fruits[j][0] - startPos <= k:\n",
    "                    tot += fruits[j][1]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    break\n",
    "            ans = max(ans, tot)\n",
    "            j -= 1\n",
    "            t = i - 1\n",
    "            #print(\"j = \", j)\n",
    "            while j >= 0 and fruits[j][0] >= startPos:\n",
    "                left = k - (fruits[j][0] - startPos)\n",
    "                #print(left)\n",
    "                if left > 0:\n",
    "                    while t >= 0:\n",
    "                        # 分类讨论：\n",
    "                        # 1. 先往左(*2)再往后 (startPos - fruits[t][0]) * 2 <= left\n",
    "                        # 2. 先往右(*2)再往左 startPos - fruits[t][0] + 2 * (fruits[j][0] - startPos) <= k\n",
    "                        if (startPos - fruits[t][0]) * 2 <= left or startPos - fruits[t][0] + 2 * (fruits[j][0] - startPos) <= k:\n",
    "                            tot += fruits[t][1]\n",
    "                            t -= 1\n",
    "                        else:\n",
    "                            break\n",
    "                    ans = max(ans, tot)\n",
    "                tot -= fruits[j][1]\n",
    "                j -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        \n",
    "        left = [[pos, a] for pos, a in fruits if pos <= startPos]\n",
    "        right = [[pos, a] for pos, a in fruits if pos > startPos]\n",
    "        m, n = len(left), len(right)\n",
    "        right.sort()\n",
    "        left.sort(reverse=True)\n",
    "        ans = 0\n",
    "  \n",
    "\n",
    "        cur = 0\n",
    "        i = -1\n",
    "        left_cnt = 0\n",
    "        while i+1<m and startPos - left[i+1][0] <= k:\n",
    "            left_cnt += left[i+1][1]\n",
    "            i += 1\n",
    "            \n",
    "        for pos, a in right:\n",
    "            if pos - startPos > k:\n",
    "                break\n",
    "            cur += a\n",
    "            while i>=0 and pos-startPos + 2*(startPos-left[i][0]) > k:\n",
    "                left_cnt -= left[i][1]\n",
    "                i -= 1\n",
    "                 \n",
    "            if cur+left_cnt > ans:\n",
    "                ans = cur+left_cnt\n",
    "\n",
    "        cur = 0\n",
    "        i = -1\n",
    "        right_cnt = 0\n",
    "        while i + 1 < n and right[i + 1][0] - startPos <= k:\n",
    "            right_cnt += right[i + 1][1]\n",
    "            i += 1\n",
    "\n",
    "        for pos, a in left:\n",
    "            if startPos - pos > k:\n",
    "                break\n",
    "            cur += a\n",
    "            while i >= 0 and startPos - pos + 2 * (right[i][0]-startPos) > k:\n",
    "                right_cnt -= right[i][1]\n",
    "                i -= 1\n",
    "\n",
    "            if cur + right_cnt > ans:\n",
    "                ans = cur + right_cnt\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = bisect_left(fruits, [startPos - k])  # 向左最远能到 fruits[left][0]\n",
    "        ans = s = 0\n",
    "        for pos, amount in fruits[left:]:\n",
    "            if pos > startPos + k: break\n",
    "            s += amount\n",
    "            while pos * 2 - fruits[left][0] - startPos > k and \\\n",
    "                  pos - fruits[left][0] * 2 + startPos > k:\n",
    "                s -= fruits[left][1]  # fruits[left][0] 无法到达\n",
    "                left += 1\n",
    "            ans = max(ans, s)  # 更新答案最大值\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "\n",
    "        n = len(fruits)\n",
    "        #fruits.sort() \n",
    "\n",
    "\n",
    "\n",
    "        f = [0] * (n + 1) \n",
    "        for i in range(1, n+1):\n",
    "            f[i] = f[i-1] + fruits[i-1][1] \n",
    "        \n",
    "        def lower_bound(x, l, r):\n",
    "            while l < r:\n",
    "                mid = (l + r) >> 1 \n",
    "                if fruits[mid][0] >= x:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l \n",
    "        \n",
    "\n",
    "        # left -> right. \n",
    "        ans = 0\n",
    "        for kk in range(k//2+1):\n",
    "            left = lower_bound(startPos-kk, 0, n) \n",
    "            right = lower_bound(startPos+k - kk*2+1, 0, n) \n",
    "            ans = max(ans, f[right] - f[left])\n",
    "        \n",
    "        # right -> left \n",
    "        for kk in range(k//2+1):\n",
    "            left = lower_bound(startPos - k + kk * 2, 0, n) \n",
    "            right = lower_bound(startPos + kk+1, 0, n) \n",
    "            ans = max(ans, f[right] - f[left]) \n",
    "        \n",
    "        return ans  \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        result = 0\n",
    "        left = 0\n",
    "        tmp = 0 \n",
    "        #i表示左下标\n",
    "        #j表示右下标\n",
    "        for right, (position, amount) in enumerate(fruits):\n",
    "            #fruits[i][0]表示左边的位置\n",
    "            #fruits[j][0]表示右边的位置\n",
    "            #fj表示草莓的数量\n",
    "            tmp += amount\n",
    "            while left <= right and position - fruits[left][0] + min(abs(startPos - fruits[left][0]), abs(startPos - fruits[right][0])) > k:\n",
    "                tmp -= fruits[left][1]\n",
    "                left += 1\n",
    "            result = max(result, tmp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        inf = float('inf')\n",
    "        accu = list(accumulate(amount for _, amount in fruits))\n",
    "        result = 0\n",
    "        # left*2 + right <= k\n",
    "        r1 = bisect_right(fruits, [startPos, 0]) \n",
    "        r2 = bisect_right(fruits, [startPos + k, inf])\n",
    "        lastLOff = inf\n",
    "        for roff in range(r2-1, r1-1, -1):\n",
    "            lLen = (k - fruits[roff][0] + startPos) >> 1\n",
    "            loff = bisect_right(fruits, [startPos - lLen, 0])\n",
    "            if loff == lastLOff:\n",
    "                continue\n",
    "            lastLOff = loff\n",
    "            result = max(result, accu[roff] - (accu[loff-1] if loff else 0))\n",
    "        # left + right *2 <= k\n",
    "        l1 = bisect_right(fruits, [startPos - k, 0])\n",
    "        l2 = bisect_right(fruits, [startPos, inf])\n",
    "        lastROff = -1\n",
    "        for loff in range(l1, l2):\n",
    "            rLen = (k - startPos + fruits[loff][0])>>1\n",
    "            roff = bisect_right(fruits, [startPos + rLen, inf])\n",
    "            if lastROff == roff: continue\n",
    "            lastROff = roff\n",
    "            result = max(result, accu[roff-1] - (accu[loff-1] if loff else 0))\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n=len(fruits)\n",
    "        pre_sum=[0]*(n+1)\n",
    "        pos=[i[0] for i in fruits]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            pre_sum[i+1]=pre_sum[i]+fruits[i][1]\n",
    "        for x in range(k,-1,-1):\n",
    "            y=(k-x)//2\n",
    "            l,r=startPos-x,startPos+y\n",
    "            pl,pr=bisect.bisect_left(pos,l),bisect.bisect_right(pos,r)\n",
    "            res=max(res,pre_sum[pr]-pre_sum[pl])\n",
    "            l,r=startPos-y,startPos+x\n",
    "            pl,pr=bisect.bisect_left(pos,l),bisect.bisect_right(pos,r)\n",
    "            res=max(res,pre_sum[pr]-pre_sum[pl])\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        \n",
    "        left = [[pos, a] for pos, a in fruits if pos <= startPos]\n",
    "        right = [[pos, a] for pos, a in fruits if pos > startPos]\n",
    "        m, n = len(left), len(right)\n",
    "        left.reverse()\n",
    "        ans = 0\n",
    "  \n",
    "\n",
    "        cur = 0\n",
    "        i = -1\n",
    "        left_cnt = 0\n",
    "        while i+1<m and startPos - left[i+1][0] <= k:\n",
    "            left_cnt += left[i+1][1]\n",
    "            i += 1\n",
    "            \n",
    "        for pos, a in right:\n",
    "            if pos - startPos > k:\n",
    "                break\n",
    "            cur += a\n",
    "            while i>=0 and pos-startPos + 2*(startPos-left[i][0]) > k:\n",
    "                left_cnt -= left[i][1]\n",
    "                i -= 1\n",
    "                 \n",
    "            if cur+left_cnt > ans:\n",
    "                ans = cur+left_cnt\n",
    "\n",
    "        cur = 0\n",
    "        i = -1\n",
    "        right_cnt = 0\n",
    "        while i + 1 < n and right[i + 1][0] - startPos <= k:\n",
    "            right_cnt += right[i + 1][1]\n",
    "            i += 1\n",
    "\n",
    "        for pos, a in left:\n",
    "            if startPos - pos > k:\n",
    "                break\n",
    "            cur += a\n",
    "            while i >= 0 and startPos - pos + 2 * (right[i][0]-startPos) > k:\n",
    "                right_cnt -= right[i][1]\n",
    "                i -= 1\n",
    "\n",
    "            if cur + right_cnt > ans:\n",
    "                ans = cur + right_cnt\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        def lowerBound(arr, left, right, val):\n",
    "            res = right + 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr[mid] >= val:\n",
    "                    res = mid\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return res\n",
    "        \n",
    "        def upperBound(arr, left, right, val):\n",
    "            res = right + 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if arr[mid] > val:\n",
    "                    res = mid\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return res\n",
    "        n = len(fruits)\n",
    "        sum = [0 for i in range(n+1)]\n",
    "        indices = []\n",
    "        for i in range(n):\n",
    "            sum[i+1] = sum[i] + fruits[i][1]\n",
    "            indices.append(fruits[i][0])\n",
    "        res = 0\n",
    "        for x in range(k//2+1):  # left\n",
    "            y = k - 2 * x\n",
    "            left = startPos - x\n",
    "            right = startPos + y\n",
    "            start = lowerBound(indices, 0, n-1, left)\n",
    "            end = upperBound(indices, 0, n-1, right)\n",
    "            res = max(res, sum[end] - sum[start])\n",
    "            \n",
    "            y = k - 2 * x\n",
    "            left = startPos - y\n",
    "            right = startPos + x\n",
    "            start = lowerBound(indices, 0, n-1, left)\n",
    "            end = upperBound(indices, 0, n-1, right)\n",
    "            res = max(res, sum[end] - sum[start])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        a, b = startPos - k, startPos + k\n",
    "        fruits = [i for i in fruits if a <= i[0] <= b]\n",
    "        if not fruits:\n",
    "            return 0\n",
    "        a = [i[0] - startPos for i in fruits]\n",
    "        b = tuple(accumulate(i[1] for i in fruits))\n",
    "\n",
    "        def f(i, j):\n",
    "            if j < a[0]:\n",
    "                return 0\n",
    "            j = b[bisect_right(a, j) - 1]\n",
    "            if i <= a[0]:\n",
    "                return j\n",
    "            return j - b[bisect_left(a, i) - 1]\n",
    "\n",
    "        t = k >> 1\n",
    "        s1, s2 = set(), set()\n",
    "        for i in a:\n",
    "            if i < -t or i > t:\n",
    "                continue\n",
    "            if i < 0:\n",
    "                s1.add(i)\n",
    "                s2.add(k + i >> 1)\n",
    "            else:\n",
    "                s2.add(i)\n",
    "                s1.add((i - k) // 2)\n",
    "        return max(chain((f(-k, 0), f(0, k)), (f(i, k + 2 * i) for i in s1), (f(2 * i - k, i) for i in s2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        left = bisect_left(fruits,[startPos-k])\n",
    "        right = bisect_left(fruits,[startPos+1])\n",
    "        res = s =  sum(c for _,c in fruits[left:right])\n",
    "        while right < n and fruits[right][0] <= startPos + k:\n",
    "            s += fruits[right][1]\n",
    "            while startPos+fruits[right][0]-2*fruits[left][0] > k and 2*fruits[right][0]-startPos-fruits[left][0] > k:\n",
    "                s -= fruits[left][1]\n",
    "                left+=1\n",
    "            print(\"===\",left,\":\",right)\n",
    "            res = max(res, s)\n",
    "            right += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        i, j = 0, 0\n",
    "        left, right, ans = [], [0], 0\n",
    "        while j < len(fruits):\n",
    "            if i < startPos:\n",
    "                if i == fruits[j][0]:\n",
    "                    left.append(fruits[j][1])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    left.append(0)\n",
    "            elif i == startPos and i == fruits[j][0]:\n",
    "                ans = fruits[j][1]\n",
    "                j += 1\n",
    "            elif i > startPos:\n",
    "                if i == fruits[j][0]:\n",
    "                    right.append(right[-1] + fruits[j][1])\n",
    "                    j += 1\n",
    "                else:\n",
    "                    right.append(right[-1])\n",
    "            i += 1\n",
    "        if i < startPos:\n",
    "            left += [0] * (startPos - len(left))\n",
    "\n",
    "        if k == 0:\n",
    "            return ans\n",
    "        for i in range(len(left) - 2, -1, -1):\n",
    "            left[i] += left[i + 1]\n",
    "\n",
    "        ll, rr = len(left), len(right) - 1\n",
    "        if ll == 0:\n",
    "            return ans + right[min(k, rr)]\n",
    "        if rr == 0:\n",
    "            return ans + left[-min(k, ll)]\n",
    "\n",
    "        def check(n):\n",
    "            if right[min(k,rr)] >= n or left[-min(k, ll)] >= n:\n",
    "                return True\n",
    "            for i in range(1, k):\n",
    "                if i <= k // 3:\n",
    "                    if left[-min(i,ll)] + right[min(k - 2 * i, rr)] >= n:\n",
    "                        return True\n",
    "                else:\n",
    "                    if (k - i) % 2 == 0:\n",
    "                        if left[-min(i, ll)] + right[min((k - i) // 2, rr)] >= n:\n",
    "                            return True\n",
    "            return False\n",
    "        l, r = 0, 1000000005\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return ans + r - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        \n",
    "        leftlimit = startPos - k\n",
    "        n = len(fruits)\n",
    "        left_ans = right_ans = 0\n",
    "        left = right = -1\n",
    "        left2 = -1\n",
    "        right2 = -1\n",
    "        if n == 1:\n",
    "            return fruits[0][1] if abs(startPos - fruits[0][0]) <= k else 0\n",
    "        \n",
    "        for i, (p, _) in enumerate(fruits):\n",
    "            if p < leftlimit:\n",
    "                continue\n",
    "            if startPos < p:\n",
    "                break\n",
    "            left = i\n",
    "            for j in range(left, n):\n",
    "                if startPos >= fruits[j][0]:\n",
    "                    left_ans += fruits[j][1]\n",
    "                else:\n",
    "                    left2 = j\n",
    "                    break\n",
    "            break\n",
    "        rightlimit = startPos + k\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            p, _ = fruits[i]\n",
    "            if p > rightlimit:\n",
    "                continue\n",
    "            if startPos > p:\n",
    "                break\n",
    "            right = i\n",
    "            for j in range(right, -1, -1):\n",
    "                if startPos <= fruits[j][0]:\n",
    "                    right_ans += fruits[j][1]\n",
    "                else:\n",
    "                    right2 = j\n",
    "                    break\n",
    "            break\n",
    "                \n",
    "                        \n",
    "        ret = max(left_ans, right_ans)\n",
    "        print(left_ans, right_ans)\n",
    "        if left != -1 and left2 != -1:\n",
    "            limit = left2\n",
    "            for i in range(left, left2):\n",
    "                dis = (startPos - fruits[i][0]) * 2\n",
    "                if i != left:\n",
    "                    left_ans -= fruits[i - 1][1]\n",
    "                while limit < n and fruits[limit][0] - startPos + dis <= k:\n",
    "                    left_ans += fruits[limit][1]\n",
    "                    limit += 1\n",
    "                print(111, left_ans)\n",
    "                ret = max(ret, left_ans)\n",
    "        if right != -1 and right2 != -1:\n",
    "            limit = right2\n",
    "            for i in range(right, right2, -1):\n",
    "                dis = (fruits[i][0] - startPos) * 2\n",
    "                if i != right:\n",
    "                    right_ans -= fruits[i + 1][1]\n",
    "                while limit >= 0 and startPos - fruits[limit][0] + dis <= k:\n",
    "                    right_ans += fruits[limit][1]\n",
    "                    limit -= 1\n",
    "                print(222,right_ans)\n",
    "                ret = max(ret, right_ans)\n",
    "        return ret\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        for i in range(1, len(fruits)):\n",
    "            fruits[i][1] += fruits[i - 1][1]\n",
    "        fruits = [[- 1, 0]] + fruits + [[2 * 10 ** 5 + 1, fruits[-1][-1]]]\n",
    "        print(fruits)\n",
    "        res = 0\n",
    "        for x in range(k + 1):\n",
    "            y = (k - x) // 2 \n",
    "            left = bisect.bisect_left(fruits, [max(0, startPos - x), ])\n",
    "            right = bisect.bisect_right(fruits, [min(2 * 10 ** 5 + 1, startPos + y), ])\n",
    "            if fruits[right][0] == min(2 * 10 ** 5 + 1, startPos + y):\n",
    "                res = max(res, fruits[right][1] - fruits[left - 1][1])\n",
    "            else:\n",
    "                res = max(res, fruits[right - 1][1] - fruits[left - 1][1])\n",
    "            left = bisect.bisect_left(fruits, [max(0, startPos - y), ])\n",
    "            right = bisect.bisect_right(fruits, [min(2 * 10 ** 5 + 1, startPos + x), ])\n",
    "            if fruits[right][0] == min(2 * 10 ** 5 + 1, startPos + x):\n",
    "                res = max(res, fruits[right][1] - fruits[left - 1][1])\n",
    "            else:\n",
    "                res = max(res, fruits[right - 1][1] - fruits[left - 1][1])\n",
    "        return res \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        for i in range(1, len(fruits)):\n",
    "            fruits[i][1] += fruits[i - 1][1]\n",
    "        fruits = [[- 1, 0]] + fruits + [[2 * 10 ** 5 + 1, fruits[-1][-1]]]\n",
    "        print(fruits)\n",
    "        res = 0\n",
    "        for x in range(k + 1):\n",
    "            y = (k - x) // 2 \n",
    "            left = bisect.bisect_left(fruits, [max(0, startPos - x), ])\n",
    "            right = bisect.bisect_right(fruits, [min(2 * 10 ** 5 + 1, startPos + y), ])\n",
    "            if fruits[right][0] == min(2 * 10 ** 5 + 1, startPos + y):\n",
    "                res = max(res, fruits[right][1] - fruits[left - 1][1])\n",
    "            else:\n",
    "                res = max(res, fruits[right - 1][1] - fruits[left - 1][1])\n",
    "            left = bisect.bisect_left(fruits, [max(0, startPos - y), ])\n",
    "            right = bisect.bisect_right(fruits, [min(2 * 10 ** 5 + 1, startPos + x), ])\n",
    "            if fruits[right][0] == min(2 * 10 ** 5 + 1, startPos + x):\n",
    "                res = max(res, fruits[right][1] - fruits[left - 1][1])\n",
    "            else:\n",
    "                res = max(res, fruits[right - 1][1] - fruits[left - 1][1])\n",
    "        return res \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        v, p, ans = [0], [], 0\n",
    "        for i in range(len(fruits)):\n",
    "            v.append(v[-1] + fruits[i][1])\n",
    "            p.append(fruits[i][0])\n",
    "\n",
    "        for x in range(k // 2 + 1):\n",
    "            y = k - 2 * x\n",
    "            # <---\n",
    "            left, right = startPos - x, startPos + y\n",
    "            start = bisect.bisect_left(p, left)\n",
    "            end = bisect.bisect_right(p, right)\n",
    "            ans = max(ans, v[end] - v[start])\n",
    "            print(start, end)\n",
    "            # --->\n",
    "            left, right = startPos - y, startPos + x\n",
    "            start = bisect.bisect_left(p, left)\n",
    "            end = bisect.bisect_right(p, right)\n",
    "            ans = max(ans, v[end] - v[start])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        l=r=ans=temp=0\n",
    "        for r,(r_i,r_n) in enumerate(fruits):\n",
    "            temp+=r_n\n",
    "            while l<=r and r_i-fruits[l][0]+min(abs(startPos-r_i),abs(startPos-fruits[l][0]))>k:\n",
    "                temp-=fruits[l][1]\n",
    "                l+=1\n",
    "            ans=max(ans,temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "      n = fruits[-1][0] + 1\n",
    "      pre = [0] * (n + 1)\n",
    "      f = [0] * (n + 1)\n",
    "      for fruit in fruits:\n",
    "        f[fruit[0]] = fruit[1]\n",
    "      for i in range(1, n + 1, 1):\n",
    "        pre[i] = pre[i-1] + f[i-1]\n",
    "      \n",
    "      def query(l, r):\n",
    "        l = max(l, 0)\n",
    "        r = min(r, n - 1)\n",
    "        if l > n or r < 0 or l > r:\n",
    "          return 0\n",
    "        return pre[r+1] - pre[l]\n",
    "\n",
    "      ans = 0\n",
    "\n",
    "      for l in range(0, int(k/2) + 1, 1):\n",
    "        r = k - 2 * l\n",
    "        ans = max(ans, query(startPos - l, startPos + r))\n",
    "      for r in range(0, int(k/2) + 1, 1):\n",
    "        l = k - 2 * r\n",
    "        ans = max(ans, query(startPos - l, startPos + r))\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        n = len(fruits)\n",
    "        sum = 0\n",
    "        ans = 0\n",
    "\n",
    "        def step(left: int, right: int) -> int:\n",
    "            if fruits[right][0] <= startPos:\n",
    "                return startPos - fruits[left][0]\n",
    "            elif fruits[left][0] >= startPos:\n",
    "                return fruits[right][0] - startPos\n",
    "            else:\n",
    "                return min(abs(startPos - fruits[right][0]), abs(startPos - fruits[left][0])) + \\\n",
    "                    fruits[right][0] - fruits[left][0]\n",
    "\n",
    "        # 每次固定住窗口右边界\n",
    "        while right < n:\n",
    "            sum += fruits[right][1]\n",
    "            # 移动左边界\n",
    "            while left <= right and step(left, right) > k:\n",
    "                sum -= fruits[left][1]\n",
    "                left += 1\n",
    "\n",
    "            ans = max(ans, sum)\n",
    "            right += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        #计算startPos出发，i到j区域经过总共需要走的步数\n",
    "        def getStep(i, j):\n",
    "            if i > j:\n",
    "                i, j = j, i\n",
    "            nonlocal startPos\n",
    "            if i <= j <= startPos:\n",
    "                return startPos - i\n",
    "            elif i <= startPos <= j:\n",
    "                return (j - i) + min(startPos - i, j - startPos)\n",
    "            elif startPos <= i <= j:\n",
    "                return j - startPos\n",
    "\n",
    "        nums = [ 0 ] * (max(fruits[-1][0], startPos) + 1)\n",
    "        for p, a in fruits:\n",
    "            nums[p] = a\n",
    "        \n",
    "        left, right = max(startPos - k , 0), startPos\n",
    "        N = len(fruits)\n",
    "        ans = 0\n",
    "        # print(nums, left, right)\n",
    "        s = sum(nums[left: right])\n",
    "        while right <= len(nums) - 1:\n",
    "            s += nums[right]\n",
    "            while left <= right and getStep(left, right) > k:\n",
    "                s -= nums[left]\n",
    "                left += 1\n",
    "            if getStep(left, right) <= k:\n",
    "                ans = max(ans, s)\n",
    "            right += 1\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        mostOne = 0\n",
    "        sum = 0\n",
    "        l = 0\n",
    "        for r in range(n):\n",
    "            sum += fruits[r][1]\n",
    "            while l <= r and (fruits[r][0] - fruits[l][0] + min(abs(startPos - fruits[l][0]), abs(startPos - fruits[r][0]))) > k:\n",
    "                sum -= fruits[l][1]\n",
    "                l = l + 1\n",
    "            mostOne = max(mostOne, sum)\n",
    "        return mostOne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        # 问题的本质在于线段覆盖水果的个数\n",
    "        n = len(fruits)\n",
    "        left,right = 0,0\n",
    "        sums = 0\n",
    "        ans = 0 \n",
    "\n",
    "        def step(left,right):\n",
    "            # 记录[pos[left],pos[right]]需要移动的步数: left,right只记录索引\n",
    "            return fruits[right][0]-fruits[left][0]+min(abs(fruits[right][0] -startPos),abs(fruits[left][0] - startPos))\n",
    "        \n",
    "        # 每次固定窗口右边界\n",
    "        while right < n:\n",
    "            sums += fruits[right][1]\n",
    "            # 移动左边界\n",
    "            while left <= right and step(left,right) > k:\n",
    "                sums -= fruits[left][1]\n",
    "                left += 1\n",
    "            ans = max(ans,sums)\n",
    "            right += 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        pos=[x[0] for x in fruits]\n",
    "        left,right=bisect.bisect_left(pos,startPos-k),bisect.bisect_right(pos,startPos+k)\n",
    "        ans=s=0\n",
    "        for i,j in fruits[left:right]:\n",
    "            s+=j\n",
    "            while 2*i-k-startPos-fruits[left][0]>0 and i+startPos-k-2*fruits[left][0]>0:\n",
    "                s-=fruits[left][1]\n",
    "                left+=1\n",
    "            ans=max(ans,s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        mostOne = 0\n",
    "        sum = 0\n",
    "        l = 0\n",
    "        for r in range(n):\n",
    "            sum += fruits[r][1]\n",
    "            while l <= r and (fruits[r][0] - fruits[l][0] + min(abs(startPos - fruits[l][0]), abs(startPos - fruits[r][0]))) > k:\n",
    "                sum -= fruits[l][1]\n",
    "                l = l + 1\n",
    "            mostOne = max(mostOne, sum)\n",
    "        return mostOne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        n = len(fruits)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        index = [0] * (n)\n",
    "        for i in range(1, n + 1):\n",
    "            pre_sum[i] = pre_sum[i - 1] + fruits[i - 1][1]\n",
    "            index[i - 1] = fruits[i - 1][0]\n",
    "        res = 0\n",
    "        for x in range(k // 2 + 1):\n",
    "            y = k - 2 * x\n",
    "            left = startPos - x\n",
    "            right = startPos + y\n",
    "            start = bisect.bisect_left(index, left)\n",
    "            end = bisect.bisect_right(index, right)\n",
    "            res = max(res, pre_sum[end] - pre_sum[start])\n",
    "            y = k - 2 * x \n",
    "            left = startPos - y\n",
    "            right = startPos + x\n",
    "            start = bisect.bisect_left(index, left)\n",
    "            end = bisect.bisect_right(index, right)\n",
    "            res = max(res, pre_sum[end] - pre_sum[start])\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        v, p, ans = [0], [], 0\n",
    "        for i in range(len(fruits)):\n",
    "            v.append(v[-1] + fruits[i][1])\n",
    "            p.append(fruits[i][0])\n",
    "\n",
    "        for x in range(k // 2 + 1):\n",
    "            y = k - 2 * x\n",
    "            # <---\n",
    "            left, right = startPos - x, startPos + y\n",
    "            start = bisect.bisect_left(p, left)\n",
    "            end = bisect.bisect_right(p, right)\n",
    "            ans = max(ans, v[end] - v[start])\n",
    "            print(start, end)\n",
    "            # --->\n",
    "            left, right = startPos - y, startPos + x\n",
    "            start = bisect.bisect_left(p, left)\n",
    "            end = bisect.bisect_right(p, right)\n",
    "            ans = max(ans, v[end] - v[start])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        #解题关键在于，需要想到从startPos开始，走完一个特定区间里的所有positions的最小步数是确定的，这个最小步数只和那个区间的左右边界相关。\n",
    "        def cost(lower, upper):\n",
    "            #返回startPos开始，走完[lower,upper]区间所需的最小步数'''\n",
    "            return min(abs(startPos-lower), abs(startPos-upper))+upper-lower\n",
    "        \n",
    "        # 滑动窗口区间[left,right]，winSum为区间内的草莓总数\n",
    "        left, right, winSum = 0, 0, 0\n",
    "        ans = 0\n",
    "        while right < len(fruits):\n",
    "            winSum += fruits[right][1]\n",
    "            while cost(fruits[left][0], fruits[right][0]) > k and left < right:\n",
    "                winSum -= fruits[left][1]\n",
    "                left += 1\n",
    "            if cost(fruits[left][0], fruits[right][0]) > k:\n",
    "                # 若当前窗口不可及，窗口左右指针要一起移动\n",
    "                winSum -= fruits[left][1]\n",
    "                right += 1\n",
    "                left += 1\n",
    "            else:\n",
    "                ans = max(ans, winSum)\n",
    "                right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        ans=0\n",
    "        l=0\n",
    "        n=len(fruits)\n",
    "        s=0\n",
    "        for r in range(n):\n",
    "            rp=fruits[r][0]\n",
    "            rf=fruits[r][1]\n",
    "            s=s+rf\n",
    "            while l <= r and rp-fruits[l][0]+ min(abs(startPos-fruits[l][0]),abs(startPos-fruits[r][0]))>k:\n",
    "                s=s-fruits[l][1]\n",
    "                l=l+1\n",
    "            ans=max(s,ans)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "    \n",
    "        fruits = [[float('-inf'), 0]] + fruits\n",
    "        fruits.append([float('inf'), 0]) \n",
    "\n",
    "        n = len(fruits)\n",
    "        f = [ 0] * n \n",
    "        for i in range(1,n):\n",
    "            f[i] = f[i-1] + fruits[i][1] \n",
    "        \n",
    "        def binsearch(x):\n",
    "            l, r = 0, n-1\n",
    "            while l <r :\n",
    "                mid= (l+r+1)>>1\n",
    "                if fruits[mid][0] <= x:\n",
    "                    l = mid \n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return l \n",
    "        \n",
    "        ans = 0\n",
    "        for k1 in range(k//2+1):\n",
    "            right = k1 \n",
    "            left = k - k1 * 2 \n",
    "            pr = binsearch(startPos+right)\n",
    "            pl = binsearch(startPos-left) \n",
    "            if startPos - left == fruits[pl][0]:\n",
    "                pl-=1 \n",
    "            ans = max(ans, f[pr] - f[pl]) \n",
    "\n",
    "        for k2 in range(k//2+1):\n",
    "            left = k2 \n",
    "            right = k - k2 * 2 \n",
    "            pr = binsearch(startPos + right)\n",
    "            pl = binsearch(startPos - left)\n",
    "            if startPos - left == fruits[pl][0]:\n",
    "                pl-=1 \n",
    "            ans = max(ans, f[pr] - f[pl]) \n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        j = 0\n",
    "        while j < len(fruits) and startPos >= fruits[j][0]:\n",
    "            j += 1\n",
    "        f1 = fruits[:j]\n",
    "        f1 = f1[::-1]\n",
    "        res = 0\n",
    "        res0 = 0\n",
    "        if len(f1) !=0 and f1[0][0]==startPos:\n",
    "            res0 = f1[0][1]\n",
    "            f1 = f1[1:]\n",
    "            \n",
    "\n",
    "        f2 = fruits[j:]\n",
    "\n",
    "        for i in range(1, len(f1)):\n",
    "            f1[i][1] += f1[i - 1][1]\n",
    "\n",
    "        for i in range(1, len(f2)):\n",
    "            f2[i][1] += f2[i - 1][1]\n",
    "\n",
    "        for i in range(len(f1)):\n",
    "            if k < startPos - f1[i][0]:\n",
    "                break\n",
    "            x = self.right(f2, startPos, k - 2 * abs(f1[i][0]-startPos))\n",
    "            mid = 0 if x == 0 else f2[x - 1][1]\n",
    "            res = max(res, res0 + f1[i][1] + mid)\n",
    "        for i in range(len(f2)):\n",
    "            if k < f2[i][0] - startPos:\n",
    "                break\n",
    "            x = self.left(f1, startPos, k - 2 * abs(f2[i][0]-startPos))\n",
    "            mid = 0 if x == 0 else f1[x - 1][1]\n",
    "            res = max(res, res0 + f2[i][1] + mid)\n",
    "        return max(res, res0)\n",
    "\n",
    "    def right(self, f: List[List[int]], startPos: int, k: int) -> int:\n",
    "        if k<=0 or len(f)==0:\n",
    "            return 0\n",
    "        if f[-1][0] - startPos <= k:\n",
    "            return len(f)\n",
    "        l = 0\n",
    "        r = len(f) - 1\n",
    "        res = 0\n",
    "        while(l<=r):\n",
    "            mid = (l+r)>>1\n",
    "            if f[mid][0] - startPos > k:\n",
    "                r = mid - 1\n",
    "                res = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return res\n",
    "    def left(self, f: List[List[int]], startPos: int, k: int) -> int:\n",
    "        if k<=0 or len(f)==0:\n",
    "            return 0\n",
    "        if startPos - f[-1][0] <= k:\n",
    "            return len(f)\n",
    "        l = 0\n",
    "        r = len(f) - 1\n",
    "        res = 0\n",
    "        while(l<=r):\n",
    "            mid = (l+r)>>1\n",
    "            if startPos - f[mid][0] > k:\n",
    "                r = mid - 1\n",
    "                res = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        # 第一步，将水果列表转换为哈希表\n",
    "        fruit_dict={fruit[0]:fruit[1] for fruit in fruits}\n",
    "        # 第二步，确定滑窗的起点和终点\n",
    "        left=max(0,startPos-k)\n",
    "        right=startPos\n",
    "        summ=sum(fruit_dict[i] for i in range(left,right+1) if i in fruit_dict)\n",
    "        ans=summ\n",
    "        while left<=startPos:\n",
    "            while True:\n",
    "                if right-left+min(startPos-left,right-startPos)>k:\n",
    "                    break\n",
    "                ans=max(ans,summ)\n",
    "                right+=1\n",
    "                summ=summ+fruit_dict[right] if right in fruit_dict else summ\n",
    "            summ=summ-fruit_dict[left] if left in fruit_dict else summ\n",
    "            left+=1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:\n",
    "        def calc(a,b):\n",
    "            x,y = startPos-a,b-startPos\n",
    "            if 2*x+y <= k or 2*y+x <= k:\n",
    "                return True\n",
    "            return False\n",
    "        n = max([a for a,_ in fruits])+1\n",
    "        l = 0 if startPos-k <= 0 else startPos-k\n",
    "        r = n-1\n",
    "        for i in range(startPos,n):\n",
    "            if not calc(l,i):r = i-1;break\n",
    "        D = {pos:v for pos,v in fruits}\n",
    "        temp = 0\n",
    "        for i in range(l,r+1):\n",
    "            if i in D:temp += D[i]\n",
    "        res = temp\n",
    "        while l < startPos:\n",
    "            if l in D:temp -= D[l]\n",
    "            l += 1\n",
    "            while r+1 < n and calc(l,r+1):\n",
    "                r += 1\n",
    "                if r in D:temp += D[r]\n",
    "            res = max(res,temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTotalFruits(self, a: List[List[int]], s: int, k: int) -> int:\n",
    "        b = [x for x, y in a]\n",
    "        b1 = [-j for j in b]\n",
    "        b1 = b1[::-1]\n",
    "        s1 = -s\n",
    "        c = [y for x, y in a]\n",
    "        c1 = c[::-1]\n",
    "\n",
    "        def  f(x, s, c):\n",
    "            n = len(x)\n",
    "            pre = {-1:0}\n",
    "            for j in range(n):\n",
    "                pre[j] = pre[j-1] + c[j]\n",
    "            if s>x[-1]:\n",
    "                return 0 \n",
    "            else:\n",
    "                j = bisect_right(x, s+k)\n",
    "                j1 = bisect_left(x, s)\n",
    "                left = j1 \n",
    "          \n",
    "                tmp = sum(c[j1:j]) \n",
    "                while (j-1)>=0 and s<=x[j-1]:\n",
    "                    j -= 1\n",
    "                    if left==0:\n",
    "                        break \n",
    "                    else:\n",
    "                        while ((left-1)>=0) and (((s-x[left-1])*2 + x[j]-s)<=k):\n",
    "                            left -= 1 \n",
    "                            tmp = max(tmp, pre[j] - pre[left-1]) \n",
    "                return tmp \n",
    "        a = f(b, s, c)\n",
    "        b = f(b1, s1, c1)\n",
    "        print(a, b)\n",
    "        ans = max(a, b)\n",
    "        return ans \n",
    "\n",
    "            \n",
    "\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
